/* Autore: Nicola Agosti */
/*
Scrivere un programma in linguaggio C che esegua l'ordinamento di un vettore di 30 numeri interi,
generati casualmente nell'intervallo [0; 99], utilizzando l'algoritmo Bubble Sort.

Link alla descrizione del Bubble Sort su Wikipedia: https://it.wikipedia.org/wiki/Bubble_sort
*/

#define _CRT_SECURE_NO_WARNINGS /* Necessario se utilizziamo Visual Studio */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUMERO_ELEMENTI 30
#define MAX_VAL 99

#define VERO 1
#define FALSO 0

int main()
{
	int numeri[NUMERO_ELEMENTI], i, j, tmp;
	int almenoUnoScambio;

	/* Riempio il vettore "numeri" con gli opportuni numeri casuali */
	srand(time(NULL));

	/* Il ciclo "for" è un modo compatto di scrivere il ciclo "while".
	L'istruzione prevede tre parti che vengono scritte tra le parentesi tonde e separate dal ";":
	  1) la prima parte è, normalmente, utilizzata per inizializzare il contatore che controlla il ciclo, 
	     il suo contenuto viene eseguito, una sola volta, la prima volta che si esegue il "for"
	  2) la seconda parte è la condizione che controlla il ciclo, funzione come nel ciclo "while"
	  3) la terza parte è, normalmente, utilizzata per incrementare il contatore che controlla il ciclo,
	     il suo contenuto viene eseguito al termine di ogni iterazione prima di testare nuovamente la condizione.
	*/
	for (i = 0; i < NUMERO_ELEMENTI; i++)
	{
		numeri[i] = rand() % (MAX_VAL + 1);
	}

	/* Visualizzo il contenuto del vettore prima dell'ordinamento */
	for (i = 0; i < NUMERO_ELEMENTI; i++)
	{
		printf("%2d ", numeri[i]);
	}

	/***************/
	/* BUBBLE SORT */
	/***************/
	
	/* Sono necessari NUMERO_ELEMENTI - 1 passi per garantire l'ordinamento dell'intero vettore */
	/* Ad ogni iterazione viene posizionato correttamente almeno un elemento */
	for (i = 0; i < NUMERO_ELEMENTI - 1; i++)
	{
		/* Confronto gli elementi del vettore a coppie a partire dall'indice 0
		e se non sono in ordine crescente li scambio */
		almenoUnoScambio = FALSO;
		for (j = 0; j < NUMERO_ELEMENTI - 1 - i; j++)
		{
			/* Verifico se l'elemento in posizione "j" è maggiore di quello in posizione "j + 1",
			se sì li scambio perchè sono in posizione errata */
			if(numeri[j] > numeri[j+1])
			{
				/* Effettuo lo scambio utilizzando una variabile di appoggio */
				tmp = numeri[j];
				numeri[j] = numeri[j + 1];
				numeri[j + 1] = tmp;

				almenoUnoScambio = VERO;
			}
		}

		/* Se non ho effettuato alcun scambio il vettore è già ordinato */
		if (almenoUnoScambio == FALSO)
		{
			break;
		}
	}

	/* Visualizzo il contenuto del vettore dopo l'ordinamento */
	printf("\n");
	for (i = 0; i < NUMERO_ELEMENTI; i++)
	{
		printf("%2d ", numeri[i]);
	}

	return 0;
}